Various methods of filling or clearing a block, or partition, of a memory are well-known in the art. For simplicity's sake, discussion hereafter will generally be limited to filling methods, as clearing methods are simply filling methods where the information stored is a null, or clear, value. The difference between storing a fill value containing a fill pattern, or a clear value containing a null pattern, is insignificant. One skilled in the art will appreciate that any disclosure relating to filling methods is equally applicable to clearing methods as well.
By a memory block or partition, we mean a logical array of memory cells, each of which is logically addressable by a unique address, the addresses typically, but not necessarily, being numerically consecutive. A memory block or partition, being organized in a logical array, is merely a virtual construct independent of the components or methods used in implementing the physical storage of the memory cells in the logical array, such as the number, sizes, types or organization of memory devices, the additional circuit components required, or the method of translation of logical addresses into physical storage addresses. By a memory cell, we mean a storage location having a physical address on a memory device, and further being logically addressable in the memory partition. A memory cell can be any number of bits in size, or width, to enable storage of a value of any numerical magnitude. By a memory, we mean the storage space for a video display system organized into a logical array of memory cells and partitioned into one or more memory partitions.
Filling and clearing methods are particularly useful in video display systems in which a memory partition is a page of video information, and where multiple partitions, or pages, may be used, or where video information is continuously updated or refreshed. Memory cells in the memory partition typically correspond to individual pixels in the display. Depending upon the number of colors or shades available for a pixel, the memory cells can range in size from 1 bit to 8 bits or more. The size of a memory partition is therefore a function of the resolution (the number of pixels in the display) and the number of available colors or shades.
Video display systems typically have one or more memory partitions, with each partition containing a complete screen of video information to be displayed. Dedicated hardware typically scans through the video information stored in the partitions continuously, to provide a video signal for display on a video display monitor. As is typical with most video display systems, a screen of information is displayed on a monitor first at the upper left corner of the display, which will typically correspond to the first memory cell in a memory partition. The memory partition is typically organized into contiguous rows of memory cells, so that the video information is read from memory cells logically addressed consecutively in the memory partition, and displayed from the left to the right in a row, then downward through each subsequent row, until the last memory cell in the memory partition has been read, and the pixel at the lower right corner of the display has been displayed. The scanning of one complete partition of memory constitutes a frame, or display update cycle, and a video display system typically displays frames at a rate of 20-60 Hertz (frames/second). The scanning of one memory cell constitutes a pixel scan cycle.
One variation on this scanning technique, interlacing, is commonly used to reduce the flicker on a video display monitor. In this technique, update frames are broken up into two or more fields which are displayed during a frame period, where each field is typically a portion of the video information in a partition of memory. Generally, a video display system has been organized to provide two fields per update frame, and to alternate between displaying the odd and even rows in a memory partition, as depicted generally in FIG. 1. Interlacing such as this provides a more pleasant display that has less flicker than non-interlaced systems. As a further improvement, fields may be started in the middle of a row, for systems in which an odd number of rows are used, such the RS-170 standard of 525 rows, where 262.5 rows are scanned per field.
Another type of interlacing technique may be used to provide additional memory access time by repeating the first field in the update frame after the second field, then starting the next update frame on the opposite field as the first field of the prior update frame, as shown in FIG. 2. In such a technique, the first update frame would consist of displaying an odd field, an even field, and an odd field, and the second update frame would consist of displaying an even field, an odd field, and an even field, etc.
A further enhancement for a display scanning method beyond interlacing is known as interlaced raster enhancement. In a system of this type, both a row and a previous row are provided to the system, so that the memory cell in the row above the current memory cell is also scanned during the pixel scan cycle for the current memory cell (i.e. (x,y) and (x,y-1)). Further, the two memory cells scanned in the previous cycle (i.e. (x-1,y) and (x-1,y-1) are stored for use with the scanning of the current memory cell. Thus, a total of four memory cells are available for each pixel scan cycle.
The interlaced raster enhancement algorithm first checks the current memory cell (x,y) to see if the memory cell contains the background value (designated "map") or overlay video information (designated "overlay"). If the memory cell contains overlay, then the contents of that memory cell are output as the pixel corresponding to the current memory cell. If the memory cell is map however, the system then successively checks the (x-1,y), (x,y-1), and (x-1,y-1) memory cells, in order, and outputs the first memory cell containing overlay information. If none of the memory cells contain overlay information, then the map information is output.
The interlaced raster enhancement improvement significantly reduces flicker in displays. In general, the current memory cell is scanned during the high portion of a pixel clock (operating at the pixel scan cycle rate), and the second memory cell in the previous row is scanned during the low portion of the pixel clock. In addition, the comparisons are not time consuming and do not require much in the way of additional hardware, so the enhancement does not decrease the speed or significantly increase the space for the system.
Another type of enhancement for video display systems is known as the ping-pong type of video display system. Such a system uses two or more memory partitions to store video information, continuously alternating between displaying the information in each partition. In a system of this type having two memory partitions, the video information in one partition is scanned and displayed while new video information is written to in the other partition (a "display update"). The partition which is currently being displayed is designated a selected memory partition, and the partition which is currently being written to, or updated, is designated a non-selected memory partition.
In a single partition video display, the system must allocate memory access between writing information to, and scanning information from, a single memory partition. In addition, care must be taken to prevent incomplete information transfers to the partition, as undesirable displays, or garbage, may result. Typically, this problem has been remedied by either blanking the screen during display updates, or by limiting memory access to the partition to the vertical retrace period, which is the period required for the electron beam of a video display to travel from the bottom of the display at the end of one field to the top of the display at the beginning of the next. The first alternative, blanking, produces a visually disruptive display which is unsuitable for many real-time applications having constant updates. The second alternative, limiting memory access, limits the amount of information that may be written to a memory partition.
The ping-pong type of system, on the other hand, allows information to be written to one memory partition while the other partition is being scanned and displayed. Information may be written without contending for memory access time, so therefore more information may be written to a memory partition. Additionally, no garbage or partial memory transfers interfere with the display. Finally, the display does not need to be blanked, so that displays requiring continuous updates will be smooth and flicker-free.
In many prior video display systems, dedicated hardware, such as a video generator, is responsible for continuously scanning information from the memory partitions, generating color data from the scanned information, and producing the various video signals necessary for displaying the information on a video display monitor. Other dedicated hardware, such as a graphics generator, is responsible for updating or writing new information to the partitions. In addition, a graphics generator or the like may also perform filling and/or clearing routines or methods. Especially in ping-pong systems, a fill or clear is performed at the beginning of each display update frame, so that new information can be written to the partition. The routine must execute in a short enough period of time to enable the graphics generator or other hardware to have sufficient time to write new information to the partition.
Typically, filling and clearing methods used in video display systems, in order to completely fill or clear a memory partition, must write, or store, information into each memory cell in the partition. The most basic of the filling methods is to consecutively write to each memory cell in the memory partition. However, each write operation on a memory cell takes a fixed amount of time. The consecutive write methods may be sufficient for small memory partitions (for low resolution displays), or for applications which are not speed-sensitive (long display rates); however, as the resolution and available colors of video displays have increased, memory and speed requirements have also increased, and a need has developed for improved routines for quickly filling a larger partition of memory.
One improvement on the basic consecutive write method of filling a memory partition is to allocate the physical storage of a memory partition between a number of memory devices, so that a write operation can be performed concurrently for a memory cell in each memory device. The time required for a fill would then be decreased by a factor of the number of memory devices which are accessed simultaneously (e.g. a fill of a memory partition allocated onto four memory devices would take 1/4 the time required with one memory device).
The advantages of this improved method ironically stem from limitations on the storage capacity of memory devices. Larger memory partitions must necessarily be allocated among a number of memory devices, due to the limited storage capacity of the memory devices. Therefore, many memory devices may be required for applications having large memory requirements.
For example, in a system having a display of 512 columns .times.512 rows, or 256K (1K=1024) pixels, each pixel being one of 256 colors or shades, 256K memory cells, each being 8-bits wide, are required in each memory partition. The state of the technology at one point required eight 32K.times.8 memory devices (the first number being the number of memory cells, the second the number of bits per cell), such as an IDT 71256 Static RAM manufactured by Integrated Device Technology. The ability to simultaneously write to eight devices provided for a fast fill time which was one-eighth of the time which would be required were each memory cell consecutively written. Assuming, for example, a graphics generator having a 125 nanosecond write time each memory cell on a memory device, this would result in a fill time (t.sub.fill) of: EQU t.sub.fill =32K.times.125ns=4.1ms
In a typical video display system having, for example, a 20 Hz display update rate, where the frame period is 50 ms, ample time is left over in the frame after a fill to write the new information to the memory partition.
The state of the technology in memory device fabrication continues to advance, and memory devices having larger storage capacities have been developed. The advances have allowed larger memory partitions to be allocated among fewer memory devices, which is particularly useful for applications having size limitations, power limitations, etc.
The state of technology now allows for the display of 512.times.512 eight-bit pixels (256K eight-bit memory cells) of the previous example to be implemented in two 256K.times.4 memory devices, such as a 41028 Static RAM chip manufactured by Paradigm Technology, Inc. However, as each memory partition is now only allocated among two devices, the fill time using the same graphics generator becomes: EQU t.sub.fill =256K.times.125ns=32.8ms
In a typical video display system having the same 20 Hz display update rate as before, over half of the frame period is taken up by the fill method, leaving little time to write the new information to the memory partition.
Therefore, a need exists in the art for a filling or clearing method which is capable of quickly filling or clearing a large memory partition, especially those in which the partition is allocated among only a few physical memory devices. In addition, in applications having size or power limitations, a further need exists for a filling or clearing method which can be implemented using minimal hardware above and beyond the hardware used in size-limited video display systems.